class Solution {
    vector<string> ret;
    string path;
    const string MAPPING[10] = {"",    "",    "abc",  "def", "ghi",
                                "jkl", "mno", "pqrs", "tuv", "wxyz"};

public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty())
            return {};
        path.resize(digits.size()); // 预先分配好空间
        dfs(digits, 0);
        return ret;
    }

    void dfs(const string& digits, int pos) {
        if (pos == digits.size()) {
            ret.push_back(path);
            return;
        }
        for (char c : MAPPING[digits[pos] - '0']) {
            path[pos] = c; 
            dfs(digits, pos + 1);
        }
    }
};
